package 树;

import 抽象数据类型.TreeNode;
import 树.遍历.LevelTraverse;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import static 树.构造树.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 路径之和为目标值 {
    //输出所有根到叶子节点的路径
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(3);
        root.right.right = new TreeNode(7);
        LevelTraverse.levelOrder(root);
        getPath(root, 7, new ArrayList<>());
    }

    public static void getPath(TreeNode root, int sum, ArrayList<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                sum -= (Integer) root.val;
                list.add((Integer) root.val);
                if (sum == 0) {
                    System.out.println(list);
                }
                root = root.left;
            }
            while (!stack.isEmpty() && (root == null || stack.peek().right == root)) {
                root = stack.pop();
                sum += (Integer) root.val;
                list.remove(list.size() - 1);
            }
            if (!stack.isEmpty()) {
                root = stack.peek().right;
            } else {
                break;
            }
        }
    }
}
